A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyrigh rights whatsoever.
1. Technical Field
The invention is related to pre-processing devices for optical character recognition systems and in particular to pre-processing devices which thin or skeletonize an image of an individual character to facilitate its recognition by an optical character recognition system.
2. Background Art
Various techniques are known in the art for thinning or skeletonizing images of patterns. Some of these techniques are directed specifically to thinning patterns of alphanumeric characters to facilitate their recognition by an optical character recognition system. Such techniques essentially strip away the outer boundary pixels of a character one layer at a time in repeated succession until the character has been sufficiently thinned. Many of these techniques avoid stripping away the end point of a character stroke under certain conditions in order to preserve the stroke. For example, Hilditch, "Linear Skeletons from Square Cupboards", Machine Intelligence, Vol. 4, Edinburgh University Press (1969) pp. 403-420 discloses thinning n image with the constraints that a pixel may not be erased if the erasure would change connectivity or if the pixel is an end point.
U.S. Pat. No. 3,975,709 (Beun et al.) discloses a character skeletonization process in which edge pixels of a character are detected by sensing their connectivity in a local neighborhood and are removed as long as such removal does not create a void in a character stroke. This process is repeated until a final repetition in which less than a threshold number of pixels are removed. Then, further repetitions of the process are performed with the added constraint that end points cannot be removed. One problem with this concept is that the shape of the skeletonized character thus generated may depend upon the sequence in which the character pixels are processed.
U.S. Pat. Nos. 3,735,349 (Beun et al.) and 4,034,344 (Saraga et al.) disclose similar concepts.
U.S. Pat. No. 3,940,737 (Beun) discloses a similar concept with an improvement directed to ameliorating the problem that the shape of the skeletonized character can depend upon the sequence in which the pixels are processed. This improvement comprises additional or repetitive testing of each pixel with respect to constraints against its removal. As in the previous references, these constraints are based upon the pixels in a local neighborhood. A disadvantage of this concept is that the additional or repetitive testing consumes additional processing time.
U.S. Pat. No. 4,162,482 (Su), U.S. Pat. No. 4,115,760 (Ito) and JP 62-160595 (Watanabe) disclose thinning processes employing different criteria during different cycles.
The main problem with such techniques is that the criteria for removing or not removing an end point of a character stroke bears no relationship to the desired results. For example, in some techniques similar to those disclosed in the publication by Hilditch referred to above, the end points are apparently preserved throughout the entire skeletonization process. As applied to alpha-numeric characters such as the letter "V", this creates distracting artifacts which may prevent the resulting thinned character from being recognized by an optical character recognition system. This may be seen by referring to the thinning sequence for the letter "V" starting with FIG. 1b and concluding with FIG. 1d. The end point 10 at the base of the letter "V" is preserved from the start (FIG. 1b) of this particular sequence as boundary pixels are removed in successive iterations, so that the letter V of FIG. 1b is converted to a letter Y in FIG. 1d. Such a result is unacceptable for optical character recognition.
The U.S. Patents to Buen et al. referred to above represent a limited improvement, in that they teach that during an initial part of the thinning process, end points are removed, provided that the connectivity criteria is not violated. Thus, starting with the letter V of FIG. 1a, all boundary pixels are removed in successive iterations until the letter has been reduced to the thinner image of FIG. 1b. Then, subsequent iterations of the boundary pixel removal step are performed with the restriction that end points may not be removed, generating the sequence of images of FIGS. 1c and 1d. In this example, the protection of the end points was begun too soon during the process. Thus, the transition point at which protection of the end pixels is begun during the thinning process is critical.
Buen et al. teaches that the protection of end points is begun during the process immediately upon the conclusion of a boundary pixel removing step at which the number of pixels actually removed was less than a predetermined threshold. There is no suggestion by Buen et al. of how to select the predetermined threshold to avoid the unacceptable results illustrated in the sequence of FIGS. 1a-1d. In the sequence of FIGS. 1a-1d, the threshold was set too high, so that the protection of end points was begun too early in the process.
If a way could be found to correctly select the point at which the protection of end points is begun during the boundary removal process, the result would be that of FIG. 2 instead of FIG. 1d. In the example of FIG. 2, the protection of the end points was not begun prematurely as in the preceding example.
The effect of beginning the protection of end points too late (or not at all) during the boundary pixel removal process is illustrated in the sequence of FIGS. 3a-3d illustrating the thinning of a letter "P". In this example, the vertical stroke 20 at the base of the "P" distinguishes the character from a letter "D". In this example, the vertical stroke 20 is somewhat thinner than the remainder of the "P", which can occur if the document containing the "P" is scanned at a high speed with a low resolution, for example. In order for an optical character recognition system to correctly recognize the thinned version of the "P", preservation of at least a distinguishing portion of the base vertical stroke 20 is critical.
In the sequence of FIGS. 3a-3d, the protection of end points is begun too late, so that the base vertical stroke 20 has been so shortened in the final thinned image of FIG. 3d that the P has been virtually converted to a letter D. This result would be reached in Buen et al. by setting their threshold number of removed pixels too high.
The ideal result is obtained by beginning the protection of end points immediately following the boundary pixel removal step of FIG. 3c. In FIG. 3c the length of the vertical base stroke 20 has been shortened to an acceptable length "a", and this length is preserved through the conclusion of the process with the result illustrated in FIG. 4.
From the foregoing, one solution might be to set the transition point at which the preservation of end points is begun to the step corresponding to that of FIG. 3c. However, while this may be the correct transition point for thinning a letter P in the sequence of FIGS. 3 and 4, it may not be the correct transition point for thinning the letter V in the sequence of FIGS. 1 and 2. Moreover, if a significant change in character size, thickness or font is encountered while scanning the document, the transition point previously selected will necessarily be incorrect for the subsequent characters.
Accordingly, there is a need for a method of determining the transition point in the thinning process at the preservation of end points is begun which avoids the formation of confusing artifacts such as that illustrated in FIG. 1d and avoids the excessive shortening of a character stroke as illustrated in FIG. 3d in a reliable and automatic manner.